package com.cat.binaryTree;

import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/reorder-list/
 * @create 2025/9/27 20:13
 * @since JDK17
 */

public class Solution73 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head, fast = head, h2;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        h2 = slow.next;
        slow.next = null;
        ListNode cur = h2, pre = null;
        while (cur != null) {
            var next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        fast = pre;
        slow = head;
        while (fast != null) {
            ListNode n1 = slow.next, n2 = fast.next;
            slow.next = fast;
            fast.next = n1;
            slow = n1;
            fast = n2;
        }
    }
}
